SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Range tree</title>

</head>

Range tree

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .infobox-subbox{padding:0;border:none;margin:-3px;width:auto;min-width:100%;font-size:100%;clear:none;float:none;background-color:transparent}.mw-parser-output .infobox-3cols-child{margin:auto}.mw-parser-output .infobox .navbar{font-size:100%}@media screen{html.skin-theme-clientpref-night .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media(min-width:640px){body.skin--responsive .mw-parser-output .infobox-table{display:table!important}body.skin--responsive .mw-parser-output .infobox-table>caption{display:table-caption!important}body.skin--responsive .mw-parser-output .infobox-table>tbody{display:table-row-group}body.skin--responsive .mw-parser-output .infobox-table th,body.skin--responsive .mw-parser-output .infobox-table td{padding-left:inherit;padding-right:inherit}}

/* end https://en.wikipedia.org/ */

</style><table class="infobox"><tbody><tr><th colspan="2" class="infobox-above">Range tree</th></tr><tr><th scope="row" class="infobox-label"><a href="List_of_data_structures" title="List of data structures">Type</a></th><td class="infobox-data">tree</td></tr><tr><th scope="row" class="infobox-label">Invented</th><td class="infobox-data">1979</td></tr><tr><th scope="row" class="infobox-label">Invented by</th><td class="infobox-data"><a href="Jon_Louis_Bentley" class="mw-redirect" title="Jon Louis Bentley">Jon Louis Bentley</a></td></tr><tr><td colspan="2" class="infobox-full-data"><table class="infobox-subbox infobox-3cols-child infobox-table"><tbody><tr><th colspan="4" class="infobox-header"><a href="Time_complexity" title="Time complexity">Time complexity</a> in <a href="Big_O_notation" title="Big O notation">big O notation</a></th></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Operation</th><td class="infobox-data infobox-data-a">

Average</td><td class="infobox-data infobox-data-b">

Worst case</td></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Search</th><td class="infobox-data infobox-data-a">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log ^{d}n+k)}</annotation>

</semantics>

</math><img src="./9312fe5a8de4d58497ddcac118796736c2d06629.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.48ex; height:3.176ex;" alt="{\displaystyle O(\log ^{d}n+k)}" loading="lazy"></td><td class="infobox-data infobox-data-b">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log ^{d}n+k)}</annotation>

</semantics>

</math><img src="./9312fe5a8de4d58497ddcac118796736c2d06629.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.48ex; height:3.176ex;" alt="{\displaystyle O(\log ^{d}n+k)}" loading="lazy"></td></tr><tr><th colspan="4" class="infobox-header"><a href="Space_complexity" title="Space complexity">Space complexity</a></th></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Space</th><td class="infobox-data infobox-data-a">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log ^{d-1}n)}</annotation>

</semantics>

</math><img src="./4a35f590b482e5c2772ac500016102d1d829200e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.311ex; height:3.176ex;" alt="{\displaystyle O(n\log ^{d-1}n)}" loading="lazy"></td><td class="infobox-data infobox-data-b">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log ^{d-1}n)}</annotation>

</semantics>

</math><img src="./4a35f590b482e5c2772ac500016102d1d829200e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.311ex; height:3.176ex;" alt="{\displaystyle O(n\log ^{d-1}n)}" loading="lazy"></td></tr></tbody></table></td></tr></tbody></table>

In <a href="Computer_science" title="Computer science">computer science</a>, a range tree is an <a href="Ordered_tree_data_structure" class="mw-redirect" title="Ordered tree data structure">ordered tree</a> <a href="Data_structure" title="Data structure">data structure</a> to hold a list of points. It allows all points within a given range to be <a href="Range_query_(computer_science)" title="Range query (computer science)">reported</a> efficiently, and is typically used in two or higher dimensions. Range trees were introduced by <a href="Jon_Louis_Bentley" class="mw-redirect" title="Jon Louis Bentley">Jon Louis Bentley</a> in 1979.<a href="#cite_note-Bentley79-1">[1]</a> Similar data structures were discovered independently by Lueker,<a href="#cite_note-Lueker78-2">[2]</a> Lee and Wong,<a href="#cite_note-LeeWong80-3">[3]</a> and Willard.<a href="#cite_note-Willard79-4">[4]</a>

The range tree is an alternative to the <a href="K-d_tree" title="K-d tree">k-d tree</a>. Compared to k-d trees, range trees offer faster query times of (in <a href="Big_O_notation" title="Big O notation">Big O notation</a>) <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log ^{d}n+k)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log ^{d}n+k)}</annotation>

</semantics>

</math><img src="./9312fe5a8de4d58497ddcac118796736c2d06629.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.48ex; height:3.176ex;" alt="{\displaystyle O(\log ^{d}n+k)}" loading="lazy"> but worse storage of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log ^{d-1}n)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log ^{d-1}n)}</annotation>

</semantics>

</math><img src="./4a35f590b482e5c2772ac500016102d1d829200e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.311ex; height:3.176ex;" alt="{\displaystyle O(n\log ^{d-1}n)}" loading="lazy">, where n is the number of points stored in the tree, d is the dimension of each point and k is the number of points reported by a given query.

In 1990, <a href="Bernard_Chazelle" title="Bernard Chazelle">Bernard Chazelle</a> improved this to query time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log ^{d-1}n+k)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log ^{d-1}n+k)}</annotation>

</semantics>

</math><img src="./d8ec3b35521f0bff4c75d53f8181797721d7f513.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.58ex; height:3.176ex;" alt="{\displaystyle O(\log ^{d-1}n+k)}" loading="lazy"> and space complexity <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O\left(n\left({\frac {\log n}{\log \log n}}\right)^{d-1}\right)}">

<mrow>

<mrow>

<msup>

<mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mrow>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O\left(n\left({\frac {\log n}{\log \log n}}\right)^{d-1}\right)}</annotation>

</semantics>

</math><img src="./85b11376867cb32e5050caecac9ad8985a2e3418.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:22.799ex; height:7.509ex;" alt="{\displaystyle O\left(n\left({\frac {\log n}{\log \log n}}\right)^{d-1}\right)}" loading="lazy">.<a href="#cite_note-Chazelle90_1-5">[5]</a><a href="#cite_note-Chazelle90_2-6">[6]</a>

<div class="mw-heading mw-heading2"><h2 id="Data_structure">Data structure</h2></div>

A range tree on a set of 1-dimensional points is a balanced <a href="Binary_search_tree" title="Binary search tree">binary search tree</a> on those points. The points stored in the tree are stored in the leaves of the tree; each internal node stores the largest value of its left subtree.

A range tree on a set of points in d-dimensions is a <a href="Recursive_data_type" title="Recursive data type">recursively defined</a> multi-level <a href="Binary_search_tree" title="Binary search tree">binary search tree</a>. Each level of the data structure is a binary search tree on one of the d-dimensions.

The first level is a binary search tree on the first of the d-coordinates. Each vertex v of this tree contains an associated structure that is a (d−1)-dimensional range tree on the last (d−1)-coordinates of the points stored in the subtree of v.

<div class="mw-heading mw-heading2"><h2 id="Operations">Operations</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Construction">Construction</h3></div>

A 1-dimensional range tree on a set of n points is a binary search tree, which can be constructed in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation>

</semantics>

</math><img src="./9d2320768fb54880ca4356e61f60eb02a3f9d9f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\displaystyle O(n\log n)}" loading="lazy"> time. Range trees in higher dimensions are constructed recursively by constructing a balanced binary search tree on the first coordinate of the points, and then, for each vertex v in this tree, constructing a (d−1)-dimensional range tree on the points contained in the subtree of v. Constructing a range tree this way would require <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log ^{d}n)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log ^{d}n)}</annotation>

</semantics>

</math><img src="./9c081c8af02814b7a0807c486f03ead35d9aebcc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.21ex; height:3.176ex;" alt="{\displaystyle O(n\log ^{d}n)}" loading="lazy"> time.

This construction time can be improved for 2-dimensional range trees to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation>

</semantics>

</math><img src="./9d2320768fb54880ca4356e61f60eb02a3f9d9f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\displaystyle O(n\log n)}" loading="lazy">.<a href="#cite_note-DutchBook3E-7">[7]</a>

Let S be a set of n 2-dimensional points. If S contains only one point, return a leaf containing that point. Otherwise, construct the associated structure of S, a 1-dimensional range tree on the y-coordinates of the points in S. Let xm be the median x-coordinate of the points. Let SL be the set of points with x-coordinate less than or equal to xm and let SR be the set of points with x-coordinate greater than xm. Recursively construct vL, a 2-dimensional range tree on SL, and vR, a 2-dimensional range tree on SR. Create a vertex v with left-child vL and right-child vR.

If we sort the points by their y-coordinates at the start of the algorithm, and maintain this ordering when splitting the points by their x-coordinate, we can construct the associated structures of each subtree in linear time.

This reduces the time to construct a 2-dimensional range tree to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation>

</semantics>

</math><img src="./9d2320768fb54880ca4356e61f60eb02a3f9d9f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\displaystyle O(n\log n)}" loading="lazy">, and also reduces the time to construct a d-dimensional range tree to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log ^{d-1}n)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log ^{d-1}n)}</annotation>

</semantics>

</math><img src="./4a35f590b482e5c2772ac500016102d1d829200e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.311ex; height:3.176ex;" alt="{\displaystyle O(n\log ^{d-1}n)}" loading="lazy">.

<div class="mw-heading mw-heading3"><h3 id="Range_queries">Range queries</h3></div>

A <a href="Range_query_(data_structures)" class="mw-redirect" title="Range query (data structures)">range query</a> on a range tree reports the set of points that lie inside a given interval. To report the points that lie in the interval [x1, x2], we start by searching for x1 and x2. At some vertex in the tree, the search paths to x1 and x2 will diverge. Let vsplit be the last vertex that these two search paths have in common. For every vertex v in the search path from vsplit to x1, if the value stored at v is greater than x1, report every point in the right-subtree of v. If v is a leaf, report the value stored at v if it is inside the query interval. Similarly, reporting all of the points stored in the left-subtrees of the vertices with values less than x2 along the search path from vsplit to x2, and report the leaf of this path if it lies within the query interval.

Since the range tree is a balanced binary tree, the search paths to x1 and x2 have length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation>

</semantics>

</math><img src="./aae0f22048ba6b7c05dbae17b056bfa16e21807d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}" loading="lazy">. Reporting all of the points stored in the subtree of a vertex can be done in linear time using any <a href="Tree_traversal" title="Tree traversal">tree traversal</a> algorithm. It follows that the time to perform a range query is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log n+k)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log n+k)}</annotation>

</semantics>

</math><img src="./1a7c999f07c8c2b6ba6e06e8532628f7e1c097b6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.388ex; height:2.843ex;" alt="{\displaystyle O(\log n+k)}" loading="lazy">, where k is the number of points in the query interval.

Range queries in d-dimensions are similar. Instead of reporting all of the points stored in the subtrees of the search paths, perform a (d−1)-dimensional range query on the associated structure of each subtree. Eventually, a 1-dimensional range query will be performed and the correct points will be reported. Since a d-dimensional query consists of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation>

</semantics>

</math><img src="./aae0f22048ba6b7c05dbae17b056bfa16e21807d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}" loading="lazy"> (d−1)-dimensional range queries, it follows that the time required to perform a d-dimensional range query is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log ^{d}n+k)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log ^{d}n+k)}</annotation>

</semantics>

</math><img src="./9312fe5a8de4d58497ddcac118796736c2d06629.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.48ex; height:3.176ex;" alt="{\displaystyle O(\log ^{d}n+k)}" loading="lazy">, where k is the number of points in the query interval. This can be reduced to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log ^{d-1}n+k)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log ^{d-1}n+k)}</annotation>

</semantics>

</math><img src="./d8ec3b35521f0bff4c75d53f8181797721d7f513.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.58ex; height:3.176ex;" alt="{\displaystyle O(\log ^{d-1}n+k)}" loading="lazy"> using a variant of <a href="Fractional_cascading" title="Fractional cascading">fractional cascading</a>.<a href="#cite_note-Lueker78-2">[2]</a><a href="#cite_note-Willard79-4">[4]</a><a href="#cite_note-DutchBook3E-7">[7]</a>

<li><a href="Segment_tree" title="Segment tree">Segment tree</a></li>

<li><a href="Range_searching" title="Range searching">Range searching</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFBentley1979" class="citation journal cs1">Bentley, J. L. (1979). <a rel="nofollow" class="external text" href="https://apps.dtic.mil/sti/pdfs/ADA061627.pdf">"Decomposable searching problems"</a> (PDF). Information Processing Letters. 8 (5): 244–251. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0020-0190%2879%2990117-0">10.1016/0020-0190(79)90117-0</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20170924023643/http://www.dtic.mil/get-tr-doc/pdf?AD=ADA061627">Archived</a> from the original on September 24, 2017.</cite>

</li>

<li id="cite_note-Lueker78-2">^ <a href="#cite_ref-Lueker78_2-0">a</a> <a href="#cite_ref-Lueker78_2-1">b</a> <cite id="CITEREFLueker1978" class="citation book cs1">Lueker, G. S. (1978). "A data structure for orthogonal range queries". 19th Annual Symposium on Foundations of Computer Science (sfcs 1978). pp. 28–21. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSFCS.1978.1">10.1109/SFCS.1978.1</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:14970942">14970942</a>.</cite>

</li>

<li id="cite_note-LeeWong80-3"><a href="#cite_ref-LeeWong80_3-0">^</a> <cite id="CITEREFLeeWong1980" class="citation journal cs1">Lee, D. T.; Wong, C. K. (1980). "Quintary trees: A file structure for multidimensional database systems". ACM Transactions on Database Systems. 5 (3): 339. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F320613.320618">10.1145/320613.320618</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2547376">2547376</a>.</cite>

</li>

<li id="cite_note-Willard79-4">^ <a href="#cite_ref-Willard79_4-0">a</a> <a href="#cite_ref-Willard79_4-1">b</a> <cite id="CITEREFWillard" class="citation techreport cs1">Willard, Dan E. The super-b-tree algorithm (Technical report). Cambridge, MA: Aiken Computer Lab, Harvard University. TR-03-79.</cite>

</li>

<li id="cite_note-Chazelle90_1-5"><a href="#cite_ref-Chazelle90_1_5-0">^</a> <cite id="CITEREFChazelle1990" class="citation journal cs1">Chazelle, Bernard (1990). <a rel="nofollow" class="external text" href="http://www.cs.princeton.edu/~chazelle/pubs/LBOrthoRangeSearchReporting.pdf">"Lower Bounds for Orthogonal Range Searching: I. The Reporting Case"</a> (PDF). Journal of the ACM. 37 (2): 200–212. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F77600.77614">10.1145/77600.77614</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:8895683">8895683</a>.</cite>

</li>

<li id="cite_note-Chazelle90_2-6"><a href="#cite_ref-Chazelle90_2_6-0">^</a> <cite id="CITEREFChazelle1990" class="citation journal cs1">Chazelle, Bernard (1990). <a rel="nofollow" class="external text" href="http://www.cs.princeton.edu/~chazelle/pubs/LBOrthoRangeSearchArithmetic.pdf">"Lower Bounds for Orthogonal Range Searching: II. The Arithmetic Model"</a> (PDF). Journal of the ACM. 37: 439–463. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F79147.79149">10.1145/79147.79149</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:15935619">15935619</a>.</cite>

</li>

<li id="cite_note-DutchBook3E-7">^ <a href="#cite_ref-DutchBook3E_7-0">a</a> <a href="#cite_ref-DutchBook3E_7-1">b</a> <cite id="CITEREFde_BergCheongvan_KreveldOvermars2008" class="citation book cs1">de Berg, Mark; Cheong, Otfried; van Kreveld, Marc; Overmars, Mark (2008). Computational Geometry. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-77974-2">10.1007/978-3-540-77974-2</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-77973-5</bdi>.</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://www.cgal.org/Manual/latest/doc_html/cgal_manual/SearchStructures/Chapter_main.html">Range and Segment Trees</a> in <a href="CGAL" title="CGAL">CGAL</a>, the Computational Geometry Algorithms Library.</li>

<li><a rel="nofollow" class="external text" href="http://www.cs.uu.nl/docs/vakken/ga/2021/slides/slides5b.pdf">Lecture 8: Range Trees</a>, Marc van Kreveld. Archived <a rel="nofollow" class="external text" href="https://archive.today/20230906153801/http://www.cs.uu.nl/docs/vakken/ga/2021/slides/slides5b.pdf">here</a>.</li>

<li><a rel="nofollow" class="external text" href="https://github.com/syhlalala/PAM/tree/master/range_query">Range Trees</a> using <a href="PAM_library" title="PAM library">PAM</a>, the parallel augmented map library.</li>

<li><a rel="nofollow" class="external text" href="https://zhoujoseph.github.io/Orthogonal-range-tree-visualization/">2D Range Tree Visualization</a>, Zhou Kaixuan.</li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Tree_data_structures246" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Tree_data_structures246" style="font-size:114%;margin:0 4em"><a href="Tree_(abstract_data_type)" title="Tree (abstract data type)">Tree data structures</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Search_tree" title="Search tree">Search trees</a> (<a href="Set_(abstract_data_type)" title="Set (abstract data type)">dynamic sets</a>, <a href="Associative_array" title="Associative array">associative arrays</a>)</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="K-D-B-tree" title="K-D-B-tree">K-Dimensional</a></li></ul></li>

<li><a href="Binary_search_tree" title="Binary search tree">Binary search</a>

<ul><li><a href="Optimal_binary_search_tree" title="Optimal binary search tree">Optimal</a></li>

<li><a href="Self-balancing_binary_search_tree" title="Self-balancing binary search tree">Self-balancing</a></li></ul></li>

<li><a href="Dancing_tree" title="Dancing tree">Dancing</a></li>

<li><a href="HTree" title="HTree">HTree</a></li>

<li><a href="Interval_tree" title="Interval tree">Interval</a></li>

<li><a href="Order_statistic_tree" title="Order statistic tree">Order statistic</a></li>

<li><a href="Palindrome_tree" title="Palindrome tree">Palindrome</a></li>

<li>(<a href="Left-leaning_red%E2%80%93black_tree" title="Left-leaning red–black tree">Left-leaning</a>) <a href="Red%E2%80%93black_tree" title="Red–black tree">Red–black</a></li>

<li><a href="Scapegoat_tree" title="Scapegoat tree">Scapegoat</a></li>

<li><a href="Splay_tree" title="Splay tree">Splay</a></li>

<li><a href="Treap" title="Treap">Treap</a></li>

<li><a href="Weight-balanced_tree" title="Weight-balanced tree">Weight-balanced</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Heap_(data_structure)" title="Heap (data structure)">Heaps</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Binary_heap" title="Binary heap">Binary</a></li>

<li><a href="Binomial_heap" title="Binomial heap">Binomial</a></li>

<li><a href="Brodal_queue" title="Brodal queue">Brodal</a></li>

<li><a href="Fibonacci_heap" title="Fibonacci heap">Fibonacci</a></li>

<li><a href="Leftist_tree" title="Leftist tree">Leftist</a></li>

<li><a href="Pairing_heap" title="Pairing heap">Pairing</a></li>

<li><a href="Skew_binomial_heap" title="Skew binomial heap">Skew binomial</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Trie" title="Trie">Tries</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Ctrie" title="Ctrie">Ctrie</a></li>

<li><a href="C-trie" title="C-trie">C-trie</a> (compressed ADT)</li>

<li><a href="Radix_tree" title="Radix tree">Radix</a></li>

<li><a href="Suffix_tree" title="Suffix tree">Suffix</a></li>

<li><a href="Ternary_search_tree" title="Ternary search tree">Ternary search</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Spatial_index" class="mw-redirect" title="Spatial index">Spatial</a> data partitioning trees</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Cartesian_tree" title="Cartesian tree">Cartesian</a></li>

<li><a href="Hilbert_R-tree" title="Hilbert R-tree">Hilbert R</a></li>

<li><a href="K-d_tree" title="K-d tree">k-d</a> (<a href="Implicit_k-d_tree" title="Implicit k-d tree">implicit k-d</a>)</li>

<li><a href="Metric_tree" title="Metric tree">Metric</a></li>

<li><a href="Octree" title="Octree">Octree</a></li>

<li><a href="Priority_R-tree" title="Priority R-tree">Priority R</a></li>

<li><a href="Segment_tree" title="Segment tree">Segment</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other trees</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Cover_tree" title="Cover tree">Cover</a></li>

<li><a href="Exponential_tree" title="Exponential tree">Exponential</a></li>

<li><a href="Fenwick_tree" title="Fenwick tree">Fenwick</a></li>

<li><a href="Finger_tree" title="Finger tree">Finger</a></li>

<li><a href="Fractal_tree_index" title="Fractal tree index">Fractal index</a></li>

<li><a href="Fusion_tree" title="Fusion tree">Fusion</a></li>

<li><a href="Hash_calendar" title="Hash calendar">Hash calendar</a></li>

<li><a href="IDistance" title="IDistance">iDistance</a></li>

<li><a href="Left-child_right-sibling_binary_tree" title="Left-child right-sibling binary tree">Left-child right-sibling</a></li>

<li><a href="Log-structured_merge-tree" title="Log-structured merge-tree">Log-structured merge</a></li>

<li><a href="Merkle_tree" title="Merkle tree">Merkle</a></li>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-23" href="https://en.wikipedia.org/wiki/?title=Range_tree&oldid=1302084633">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>